/***********************************************************************
 ** Reykjavik University
 ** Grímur Tómasson & Eiríkur Torfason
 ** Copyright (c) 2011. All rights reserved.
 **
 ** This is an implementation of a MiniMax search. It is based on the 
 ** pseudocode on p. 166 in the textbook (Russell/Norvig).
 **
 **********************************************************************/

#include "MiniMaxSearch.h"

#include <iostream>
#include <limits.h>

#include "Common.h"
#include "Utility.h"

//----------------------------------------------------------------------------------------------------------
//Declarations

int minValueMinimax( bitboard* bitboardArrayPointer[], int* currentPlyPointer, int depthLimit, int& expanded );
int maxValueMinimax( bitboard* bitboardArrayPointer[], int* currentPlyPointer, int depthLimit, int& expanded );

//----------------------------------------------------------------------------------------------------------
//
// Returns the number of the column that Max will place a token in
//
int minimaxDecision( bitboard* bitboardArrayPointer[], int* currentPlyPointer, int& depthLimit, int& expanded, int& milliseconds)
{
	//
	// Declare (and initialize) variables
	//
	int bestMove = -1;
	int bestMoveValue = INT_MIN;
	int value = 0;
	bitboard newBoard;
	//
	// Here we figure out which side is playing. We do this by looking at the current turn number. If it's an even
	// number then it's black's turn (side == 0), otherwise it's red's turn (side == 1). I guess we could use the
	// modulus operator but bitwise operators are simply more bad-ass.
	//
	int side = (*currentPlyPointer)&1;
	//
	// Initialize the by-reference parameters
	//
	expanded = 0;
	milliseconds = 0;
	//
	// Let's take stock of the current time so that we can later calculate the elapsed time
	//
	double millisecondsStart = getCurrTimeInMilliseconds();
	//
	// Iterate through the columns (possible moves)
	//
	for( int column = 0; column < WIDTH; ++column )
	{
		//
		// Let's generate a new board where we place a token in the current column
		//
		newBoard = newBoardAndMove( *bitboardArrayPointer[side], column );
		//
		// Was this a legal move or was the column full already?
		//
		if( !isLegal( newBoard ) )
		{
			//
			// We can't place a token in this column. Move on to the next column.
			//
			continue;
		}
		//
		// The move is legal. Let's make the move on the actual board.
		//
		makeMove(column);
		//
		// Now it's the min-player's turn
		//
		value = minValueMinimax( bitboardArrayPointer, currentPlyPointer, depthLimit, expanded );
		//
		// Backtrack, take back the move we just played.
		//
		undoMove();
		//
		// Show the score/value of this move
		//
		std::cout << "column: " << column << " Score: " << value << std::endl;
		//
		// Is this the best move yet?
		//
		if (value >= bestMoveValue)
		{
			bestMoveValue = value;
			bestMove = column;
		}
	}
	//
	// Calculate the elapsed time
	//
	milliseconds = getCurrTimeInMilliseconds() - millisecondsStart;
	//
	// Return the best move (column) we found
	//
	return bestMove;
}
//----------------------------------------------------------------------------------------------------------

int maxValueMinimax( bitboard* bitboardArrayPointer[], int* currentPlyPointer, int depthLimit, int& expanded )
{
	//
	// Use the turn count (ply) to figure out which color/board Max has and which color Min has
	//
	int side = (*currentPlyPointer)&1;
	int otherSide = side^1;
	//
	// Did the min-player win with the last move?
	//
	if( isLegalHasWon( *bitboardArrayPointer[otherSide] ) )
	{
		//
		// No point in going any further. Return the LOSS value.
		//
		return INT_MIN;
	}
	//
	// Have we reached the depth limit?
	//
	if( !depthLimit )
	{
		//
		// Evaluate the current board and return the value (score)
		//
		return utility( bitboardArrayPointer, currentPlyPointer, side );
	}
	//
	// Increment the number of expanded nodes/states
	//
	++expanded;
	//
	// Declare and initialize variables
	//
	int v = INT_MIN;
	bitboard newBoard;
	//
	// Iterate through the columns (possible moves)
	//
	for( int column = 0; column < WIDTH; ++column )
	{
		//
		// Let's generate a new board where we place a token in the current column
		//
		newBoard = newBoardAndMove( *bitboardArrayPointer[side], column );
		//
		// Was this a legal move or was the column full already?
		//
		if( !isLegal( newBoard ) )
		{
			//
			// We can't place a token in this column. Move on to the next column.
			//
			continue;
		}
		//
		// The move is legal. Let's make the move on the actual board.
		//
		makeMove(column);
		//
		// Now it's the min-player's turn
		//
		v = max( v, minValueMinimax( bitboardArrayPointer, currentPlyPointer, depthLimit-1, expanded ) );
		//
		// Backtrack, take back the move we just played.
		//
		undoMove();
	}
	//
	// Return the value of Max's best move
	//
	return v;
}
//----------------------------------------------------------------------------------------------------------

int minValueMinimax( bitboard* bitboardArrayPointer[], int* currentPlyPointer, int depthLimit, int& expanded )
{	
	//
	// Use the turn count (ply) to figure out which color Max has and which color Min has
	//
	int side = (*currentPlyPointer)&1;
	int otherSide = side^1;
	//
	// Did the max-player win with the last move?
	//
	if( isLegalHasWon( *bitboardArrayPointer[otherSide] ) )
	{
		//
		// No point in going any further. Return the WIN value.
		//
		return INT_MAX;
	}
	//
	// Have we reached the depth limit?
	//
	if( !depthLimit )
	{
		//
		// Evaluate the current board and return the value (score)
		//
		return utility( bitboardArrayPointer, currentPlyPointer,  side ); 
	}
	//
	// Increment the number of expanded nodes/states
	//
	++expanded;
	//
	// Declare and initialize variables
	//
	int v = INT_MAX;
	bitboard newBoard;
	//
	// Iterate through the columns (possible moves)
	//
	for( int column = 0; column < WIDTH; ++column )  //Possible moves
	{
		//
		// Let's generate a new board where we place a token in the current column
		//
		newBoard = newBoardAndMove( *bitboardArrayPointer[side], column );
		//
		// Was this a legal move or was the column full already?
		//
		if( !isLegal( newBoard ) )
		{
			//
			// We can't place a token in this column. Move on to the next column.
			//
			continue;
		}
		//
		// The move is legal. Let's make the move on the actual board.
		//
		makeMove(column);
		//
		// Now it's the max-player's turn
		//
		v = min( v, maxValueMinimax( bitboardArrayPointer, currentPlyPointer, depthLimit-1, expanded ) );
		//
		// Backtrack, take back the move we just played.
		//
		undoMove();
	}
	//
	// Return the value of Min's best move
	//
	return v;
}
//----------------------------------------------------------------------------------------------------------
